\documentclass[a4paper,10pt]{article}

%grafico
\usepackage[all]{xy}
%linguagem
\usepackage[brazil]{babel}
%encodificação
\usepackage[utf8]{inputenc}
%biblioteca de matemática
\usepackage{amssymb,amsmath}
%pacote para codigo fonte
\usepackage{listings}
%figuras
\usepackage{graphicx}
%cores
\usepackage{color}
%paragrafo no inicio da secao
\usepackage{indentfirst}
%url
\usepackage{framed, url}
\usepackage{fancyvrb}

%define a cor "claro"
\definecolor{claro}{gray}{0.96}

%configurações do fancy verbatim
\fvset{frame=single, xleftmargin=-80pt, xrightmargin=-80pt}
%configurações do listings
\lstset{language=C++,frame=trBL, numbers=left, xleftmargin=0pt, xrightmargin=0pt,
breaklines=true, backgroundcolor=\color{claro}}

\begin{document}

\input{./titulo.tex}
\tableofcontents
\pagebreak

\section{Introdução}
O problema do carteiro chinês (PCC) consistem em encontrar o menor caminho que um
carteiro deve percorrer de forma a passar por todas as ruas da cidade pelo menos
uma vez. Este trabalho visa implementar algoritmos para solucionar este
problema, obtendo soluções ótimas.

\section{Modelagem}
Para resolver o PCC podemos modelar o problema da seguinte forma:

O grafo representa a cidade e a figura \ref{fig:grafo} mostra um exemplo de modelagem.
\begin{itemize}
\item cada aresta é uma rua;
\item as arestas têm o peso definido pelo tamanho da rua;
\item nós são os cruzamentos entre ruas.
\end{itemize}

\begin{figure}[h!]
\centering
\includegraphics[scale=0.5]{imagens/cidade.png}\\
\vspace{1cm}
\includegraphics[scale=0.5]{imagens/grafo.png}
\label{fig:grafo}
\caption{Modelagem do problema utilizando grafos}
\end{figure}

\section{Solução}
Antes de obter a solução do problema, alguns conceitos devem ser explicitados:

\begin{itemize}
\item Grafo conexo: Grafo que possui pelo menos um caminho que liga todos os
nós.
\item Grafo não-direcionado: Grafo em que as arestas representam caminhos
bi-direcionais. Se existe uma aresta entre os nós A e B, então podemos caminhar
de A para B ou de B para A.
\item Grafo euleriano: Grafo que possui um caminho euleriano.
\item Circuito euleriano: Caminho que passa uma vez em cada aresta do grafo e
retorna ao ponto inicial.
\end{itemize}

A solução do PCC é obtida achando o circuito euleriano de um grafo euleriano, conexo,
não-direcionado. Os algoritmos usados para obter a solução do problema serão
explicitados. Em alto nível a abordagem foi a seguinte:

\begin{Verbatim}

lê um grafo da entrada
se o grafo não é euleriano
{
  cria grafo com nós de grau ímpar
  resolve o emparelhamento com custo mínimo
}
acha circuito euleriano
  
\end{Verbatim}

\subsection{TADs e estrutura de dados}

Para criar a abstração de grafos foi implementado um TAD utilizando listas de
adjacência. Uma {\it hashtable} contém todos os nós do grafo, e cada nó possui
uma lista de arestas. Por exemplo, o grafo a seguir:

\begin{figure}[h!]
\centering
\includegraphics[scale=0.5]{imagens/entrada.png}
\end{figure}

Seria armazenado desta forma:

\begin{figure}[h!]
\centering
\includegraphics[scale=0.5]{imagens/lista.png}
\end{figure}

\begin{lstlisting}
class Pair
{
  int node;
  int weight;
}

class Graph
{
  map<int, list<Pair> > pairMap;
  int numEdges;
  int numNodes;
}
\end{lstlisting}

\subsection{Lendo o grafo da entrada}

A entrada do programa consiste de uma sequência de arestas, obedecendo o
seguinte padrão:

\begin{Verbatim}
<nodo> <nodo> <peso>
<nodo> <nodo> <peso>
...
\end{Verbatim}

Portanto a entrada:
\begin{Verbatim}
0 1 5
1 2 5
2 0 5
\end{Verbatim}

Geraria este grafo:

\begin{figure}[h!]
\centering
\includegraphics[scale=0.5]{imagens/entrada.png}
\end{figure}

\subsection{Verificando se o grafo é euleriano}

Para saber se um grafo contém um caminho euleriano, basta todos os nós deste
grafo possuírem grau (número de arestas) par. O tamanho de cada lista de arestas
nos dá o número de arestas de cada nó do grafo.

\subsection{Resolvendo o emparelhamento a custo mínimo}
Para fazer o emparelhamento a custo mínimo, basta transformar um grafo não-Euleriano em Euleriano adicionando arestas no grafo
  \begin{enumerate}
   \item Liste todos os vértices impares $\in G$
   \item Ache todos os conjuntos possíveis de pares de vértices impares
   \item Para cada conjunto de pares, ache o menor caminho entre os pares.
  \end{enumerate}

\subsection{Achando o caminho euleriano}

Para achar o caminho euleriano usamos o algoritmo de Fleury\cite{fleury}.

\begin{Verbatim}
pega um nó inicial
enquanto existirem arestas
{
  seleciona uma aresta do nó
  se não gera grafo desconexo ou não tem outra opção
  {
    percorre esta aresta e adiciona à solução
  }
}

\end{Verbatim}

\section{Instruções para utilização}

O programa deve ser compilado utilizando o compilador {\it g++}.

\colorbox{claro}{\$ g++ graph.c -o graph.o}

\colorbox{claro}{\$ g++ graph.o -o carteirochines}

Para executar utilize o comando:

\colorbox{claro}{\$ ./carteirochines $<$ in.txt}

\section{Testes}
Os testes foram feitos utilizando arquivos de entrada contendo os dados dos
grafos a serem analisados.

\begin{enumerate}
 \item {\bf Primeiro teste}
 \subitem Arquivo de Entrada
 \begin{Verbatim}
 0 1 5
 0 2 5
 0 3 5
 1 2 5
 2 3 5
 0 2 5
 \end{Verbatim}

 \subitem Saída do Programa
 \begin{Verbatim}
 ******* Grafo Original ********
 Number of Nodes => 4
 Number of Edges => 6
 0 => [Node: 1, Weight: 5] [Node: 2, Weight: 5] [Node: 3, Weight: 5] [Node: 2,
 Weight: 5]
 1 => [Node: 0, Weight: 5] [Node: 2, Weight: 5]
 2 => [Node: 0, Weight: 5] [Node: 1, Weight: 5] [Node: 3, Weight: 5] [Node: 0,
 Weight: 5]
 3 => [Node: 0, Weight: 5] [Node: 2, Weight: 5]


 O grafo é euleriano




 ****** Circuito Euleriano *******
 0 => 1 => 2 => 0 => 3 => 2 => 0
 \end{Verbatim}
 \item {\bf Segundo teste}
  \subitem Arquivo de Entrada
  \begin{Verbatim}
	0 1 7
	1 2 9
	1 6 6
	6 2 7
	0 5 2
	5 6 8
	5 4 12
	4 3 5
	6 4 4
	6 3 4
  \end{Verbatim}
 \item Grafo de entrada

\hspace{4.0cm}    \xymatrix{
    \bullet{\ar@{-}[r]^7 \ar@{-}[d]^2}_a & \bullet{\ar@{-}[r]^9 \ar@{-}[d]^6}_b  & \bullet{\ar@{-}[dl]_7}_c      \\
    \bullet{\ar@{-}[r]^8 \ar@{-}[dr]^{12}}_f  &  \bullet{\ar@{-}[r]^4  \ar@{-}[d]^4}_g & \bullet{\ar@{-}[dl]^5}_d    \\
        & {\bullet}_e  &
    }

  \pagebreak
 \subitem Saída do Programa
  \begin{Verbatim}
  ******* Grafo Original ********
  Number of Nodes => 7
  Number of Edges => 10
  0 => [Node: 1, Weight: 7] [Node: 5, Weight: 2]
  1 => [Node: 0, Weight: 7] [Node: 2, Weight: 9] [Node: 6, Weight: 6]
  2 => [Node: 1, Weight: 9] [Node: 6, Weight: 7]
  3 => [Node: 4, Weight: 5] [Node: 6, Weight: 4]
  4 => [Node: 5, Weight: 12] [Node: 3, Weight: 5] [Node: 6, Weight: 4]
  5 => [Node: 0, Weight: 2] [Node: 6, Weight: 8] [Node: 4, Weight: 12]
  6 => [Node: 1, Weight: 6] [Node: 2, Weight: 7] [Node: 5, Weight: 8] [Node: 4, Weight: 4] 
  [Node: 3, Weight: 4]


  O grafo não é euleriano


  Caminhos duplicados: 1&5 4&6 
  Duplicando aresta 1 0
  Duplicando aresta 0 5
  Duplicando aresta 4 6


  Number of Nodes => 7
  Number of Edges => 13
  0 => [Node: 1, Weight: 7] [Node: 5, Weight: 2] [Node: 1, Weight: 7] [Node: 5, Weight: 2]
  1 => [Node: 0, Weight: 7] [Node: 2, Weight: 9] [Node: 6, Weight: 6] [Node: 0, Weight: 7]
  2 => [Node: 1, Weight: 9] [Node: 6, Weight: 7]
  3 => [Node: 4, Weight: 5] [Node: 6, Weight: 4]
  4 => [Node: 5, Weight: 12] [Node: 3, Weight: 5] [Node: 6, Weight: 4] [Node: 6, Weight: 4]
  5 => [Node: 0, Weight: 2] [Node: 6, Weight: 8] [Node: 4, Weight: 12] [Node: 0, Weight: 2]
  6 => [Node: 1, Weight: 6] [Node: 2, Weight: 7] [Node: 5, Weight: 8] [Node: 4, Weight: 4] 
  [Node: 3, Weight: 4] [Node: 4, Weight: 4]


  ****** Circuito Euleriano *******
  0 => 1 => 2 => 6 => 1 => 0 => 5 => 6 => 4 => 3 => 6 => 4 => 5 => 0
  \end{Verbatim}
  \pagebreak
  \item Grafo de Saída

\hspace{4.0cm}    \xymatrix{
    \bullet{\ar@{=}[r]^7 \ar@{=}[d]^2}_a & \bullet{\ar@{-}[r]^9 \ar@{-}[d]^6}_b  & \bullet{\ar@{-}[dl]_7}_c      \\
    \bullet{\ar@{-}[r]^8 \ar@{-}[dr]^{12}}_f  &  \bullet{\ar@{-}[r]^4  \ar@{=}[d]^4}_g & \bullet{\ar@{-}[dl]^5}_d    \\
        & {\bullet}_e  &
    }

\end{enumerate}

\clearpage
\begin{thebibliography}{99}
\bibitem{wiki} \url{http://en.wikipedia.org/wiki/Route\_inspection\_problem}
\bibitem{fleury} \url{http://www.austincc.edu/powens/+Topics/HTML/05-6/05-6.html}
\bibitem{oi} \url{http://www.professeurs.polymtl.ca/michel.gagnon/Disciplinas/Bac/Grafos/EulerHam/euler_ham.html#Euler}
\bibitem{oi2} \url{www.ams.jhu.edu/~castello/251/Handouts/ChinesePostman.doc}
\end{thebibliography}

\end{document}
